#include <iostream>
#include <iterator>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <vector>
#include <functional>
#include <boost/bind.hpp>
#include <boost/timer.hpp>
#include <boost/shared_ptr.hpp>

using namespace std;

template<typename T>
void compswap(T& a, T& b)
{
	if( a>b )
		swap<T>(a,b);
}

template<typename T>
void insertion(vector<T>& v)
{
     const int size = v.size();
     for(int i=0;i<size;++i)
        for(int j=i;j>0;--j)
            compswap(v[j-1], v[j]);
}

int cmp(const void *a, const void *b)
{
	return (*(int*)a > *(int*)b);
}

int main(int atrgc, char** argv)
{
	srand(static_cast<int>(time(0)));

	const int size = 100000;
	vector<int> V(size);
	generate(V.begin(),V.end(),rand);

	boost::timer Time;
	insertion<int>(V);
//	qsort(&*V.begin(),V.size(),sizeof(int),cmp);
	cout<<"SORTING TIME: "<<Time.elapsed()<<endl;
//	copy(V.begin(),V.end(),ostream_iterator<int>(cout, "\n"));

	return 0;
}
